package DataStructures.sort;

import java.util.Arrays;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/11 20:53
 * @description：归并排序
 * @modified By：
 * @version: $
 */
public class MergeSort {
    public static void main(String[] args) {

        int[] array = {-9, 78, 0, 23, -567, 70};
        int[] temp = new int[array.length];
        splitAndmerge(array, 0, array.length - 1, temp);

        System.out.println(Arrays.toString(array));

    }

    public static void splitAndmerge(int[] array, int left, int right, int[] temp) {
        if (left < right) {

            int mid = (left + right) / 2;
            //左边划分为一个元素的数组
            splitAndmerge(array, left, mid, temp);
            //右边划分为一个元素的数组
            splitAndmerge(array, mid + 1, right, temp);
            //合并数组
            merge(array, left, mid, right, temp);
        }
    }

    //合并
    public static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int lefti = left;
        int rightj = mid + 1;
        //temp的下标
        int t = 0;

        while (lefti <= mid && rightj <= right) {
            if (array[lefti] <= array[rightj]) {
                temp[t] = array[lefti];
                lefti++;
                t++;
            } else {
                temp[t] = array[rightj];
                rightj++;
                t++;
            }
        }
        //将左或右剩余的数字插入到array中
        while (lefti != mid) {
            temp[t] = array[lefti];
            t++;
            lefti++;
        }
        while (rightj != right) {
            temp[t] = array[rightj];
            t++;
            rightj++;
        }

        //将temp数组合并到array
        for (int i = 0; i < temp.length; i++) {
            array[i] = temp[i];
        }
    }


}